package leedcode_path.回溯;

import java.util.ArrayList;
import java.util.List;

public class 分割回文串 {
    /*
    * 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是
回文串
 。返回 s 所有可能的分割方案。
示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a"
输出：[["a"]]
 */
    List<String> path =new ArrayList<String>();
    List<List<String>> res=new ArrayList<List<String>>();
    public List<List<String>> partition(String s) {
        backtracking(s,0);
        return res;
    }
    public void backtracking(String s,int startindex){
        if (startindex> s.length()-1){
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = startindex; i <s.length() ; i++) {
            if (ishuiwen(s,startindex,i)){
                String str=s.substring(startindex,i+1);
                path.add(str);
                backtracking(s,i+1);
                path.remove(path.size()-1);
            }
        }

    }
    public boolean ishuiwen(String s,int start,int end){
        for (int i = start,j=end; i <j ; i++,j--) {
            if (s.charAt(i)!=s.charAt(j)){
                return  false;
            }
        }
        return true;
    }

}
